<!DOCTYPE html>





<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 3.9.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.ico?v=7.4.0">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.ico?v=7.4.0">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.ico?v=7.4.0">
  <link rel="mask-icon" href="/images/logo.svg?v=7.4.0" color="#222">

<link rel="stylesheet" href="/css/main.css?v=7.4.0">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '7.4.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
    copycode: {"enable":false,"show_result":false,"style":null},
    back2top: {"enable":true,"sidebar":false,"scrollpercent":false},
    bookmark: {"enable":false,"color":"#222","save":"auto"},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: 'search.json',
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    translation: {
      copy_button: '复制',
      copy_success: '复制成功',
      copy_failure: '复制失败'
    },
    sidebarPadding: 40
  };
</script>

  <meta name="description" content="1. 如何实现散列表 在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。  “桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。  当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散">
<meta name="keywords" content="dht">
<meta property="og:type" content="article">
<meta property="og:title" content="dht分布式散列表和kad介绍">
<meta property="og:url" content="https://unix2dos.github.io/p/2c46e603.html">
<meta property="og:site_name" content="Levon&#39;s Blog">
<meta property="og:description" content="1. 如何实现散列表 在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。  “桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。  当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-09-27T15:36:51.208Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="dht分布式散列表和kad介绍">
<meta name="twitter:description" content="1. 如何实现散列表 在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。  “桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。  当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散">
  <link rel="canonical" href="https://unix2dos.github.io/p/2c46e603">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: false,
    isPost: true,
    isPage: false,
    isArchive: false
  };
</script>

  <title>dht分布式散列表和kad介绍 | Levon's Blog</title>
  








  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">
  <div class="container use-motion">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Levon's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <h1 class="site-subtitle" itemprop="description">微信:  L6241425</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
      
      
      
        
        <li class="menu-item menu-item-home">
      
    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-archives">
      
    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>时光</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-categories">
      
    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-tags">
      
    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
      <li class="menu-item menu-item-search">
        <a href="javascript:;" class="popup-trigger">
        
          <i class="menu-item-icon fa fa-search fa-fw"></i> <br>搜索</a>
      </li>
    
  </ul>

</nav>
  <div class="site-search">
    <div class="popup search-popup">
    <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocorrect="off" autocapitalize="none"
           placeholder="搜索..." spellcheck="false"
           type="text" id="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result"></div>

</div>
<div class="search-pop-overlay"></div>

  </div>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
            

          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
      <article itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block post">
    <link itemprop="mainEntityOfPage" href="https://unix2dos.github.io/p/2c46e603.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Levon">
      <meta itemprop="description" content="Never Give Up">
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Levon's Blog">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">dht分布式散列表和kad介绍

          
        </h2>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              
                
              

              <time title="创建时间：2018-05-14 00:30:01" itemprop="dateCreated datePublished" datetime="2018-05-14T00:30:01+08:00">2018-05-14</time>
            </span>
          
            

            
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2019-09-27 23:36:51" itemprop="dateModified" datetime="2019-09-27T23:36:51+08:00">2019-09-27</time>
              </span>
            
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/3-计算机系统/" itemprop="url" rel="index"><span itemprop="name">3-计算机系统</span></a></span>

                
                
                  ，
                
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/3-计算机系统/BitTorrent/" itemprop="url" rel="index"><span itemprop="name">BitTorrent</span></a></span>

                
                
              
            </span>
          

          
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
        
      
      <span class="post-meta-item-text">Disqus：</span>
    
    <a title="disqus" href="/p/2c46e603.html#comments" itemprop="discussionUrl"><span class="post-comments-count disqus-comment-count" data-disqus-identifier="p/2c46e603.html" itemprop="commentCount"></span></a>
  </span>
  
  
          <br>
            <span class="post-meta-item" title="本文字数">
              <span class="post-meta-item-icon">
                <i class="fa fa-file-word-o"></i>
              </span>
              
                <span class="post-meta-item-text">本文字数：</span>
              
              <span>5.7k</span>
            </span>
          
            <span class="post-meta-item" title="阅读时长">
              <span class="post-meta-item-icon">
                <i class="fa fa-clock-o"></i>
              </span>
              
                <span class="post-meta-item-text">阅读时长 &asymp;</span>
              
              <span>5 分钟</span>
            </span>
          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h3 id="1-如何实现散列表"><a href="#1-如何实现散列表" class="headerlink" title="1. 如何实现散列表"></a>1. 如何实现散列表</h3><ul>
<li><p>在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。</p>
</li>
<li><p>“桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。</p>
</li>
<li><p>当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散列值对 N（桶数）进行“取模”运算（除法求余数），就可以算出对应的桶编号。（注：取模运算是最常用的做法，但不是唯一的做法）</p>
</li>
</ul>
<a id="more"></a>

<h3 id="2-分布式散列表-DHT"><a href="#2-分布式散列表-DHT" class="headerlink" title="2. 分布式散列表 DHT"></a>2. 分布式散列表 DHT</h3><h5 id="2-1-P2P-技术路线"><a href="#2-1-P2P-技术路线" class="headerlink" title="2.1 P2P 技术路线"></a>2.1 P2P 技术路线</h5><ul>
<li>中央服务器  Napster  -&gt;单点故障</li>
<li>广播   Gnutella 早期版本 -&gt;广播风暴</li>
<li>DHT</li>
</ul>
<h5 id="2-2-DHT-难点"><a href="#2-2-DHT-难点" class="headerlink" title="2.2 DHT 难点"></a>2.2 DHT 难点</h5><ul>
<li><p>无中心 </p>
<p>  需要提供一系列机制来实现节点之间的通讯。</p>
</li>
<li><p>海量数据 </p>
<p>  每个节点只能存储（整个系统的）一小部分数据。需要把数据【均匀分摊】到每个节点。</p>
</li>
<li><p>节点动态变化  </p>
<p>  统散列表所含的【桶数】是固定不变滴。为啥捏？因为传统散列表在针对 key 计算出散列值之后，需要用“散列值”和“桶数”进行某种运算（比如：取模运算），从而得到桶的编号。如果桶的数量出现变化，就会影响到上述“取模运算”的结果，然后导致数据错乱。</p>
</li>
<li><p>高效查询</p>
</li>
</ul>
<h5 id="2-3-DHT-难点解决"><a href="#2-3-DHT-难点解决" class="headerlink" title="2.3 DHT 难点解决"></a>2.3 DHT 难点解决</h5><ul>
<li><p>散列算法的选择</p>
<p>  DHT业务数据的散列值作为Key,业务数据为Value, 所以要避免碰撞</p>
</li>
<li><p>同构的 nodeID 和 data key</p>
<p>  DHT 属于分布式系统的一种。既然是分布式系统，意味着存在【多个】节点</p>
<p>  很多 DHT 的设计会让“node ID”采用跟“data key”【同构】的散列值。这么搞的好处是<br>  1、当散列值空间足够大的时候，随机碰撞忽略不计，因此也就确保了 node ID 的唯一性 2、可以简化系统设计——比如简化路由算法</p>
</li>
<li><p>“拓扑结构”的设计</p>
<p>  作为分布式系统，DHT 必然要定义某种拓扑结构；有了拓扑结构，自然就要设计某种“路由算法”。如果某个 DHT 采用前面所说的——“node ID”与“data key”【同构】——那么很自然的就会引入“Key-based routing”。</p>
<p>  请注意，这【不是】某个具体的路由算法，而只是某种【风格】。采用这种风格来设计路由机制，好处是：key 本身已经提供了足够多的路由信息。</p>
</li>
<li><p>“路由算法”的权衡</p>
<p>由于 DHT 中的节点数可能非常多（比如：几十万、几百万），而且这些节点是动态变化的。因此就【不可能】让每一个节点都记录所有其它节点的信息。实际情况是：每个节点通常只知道少数一些节点的信息。</p>
<p>在确定了路由算法之后，还需要做一个两难的权衡——“路由表的大小”。<br>路由表越大，可以实现越短（跳数越少）的路由；缺点是：（由于节点动态变化）路由表的维护成本也就越高。<br>路由表数越小，其维护成本越小；缺点是：路由就会变长（跳数变多）。</p>
</li>
<li><p>距离算法</p>
<p> 某些 DHT 系统还会定义一种“距离算法”，用来计算：“节点之间的距离”、“数据之间的距离”、“节点与数据的距离”。</p>
<p> 写到这里，某些聪明的读者就会明白：为啥前面要强调——“node ID”与“data key”【同构】。当这两者【同构】，就可以使用【同一种“距离算法”】；反之，如果这两者不同构，多半要引入几种不同的“距离算法”。</p>
</li>
<li><p>数据定位</p>
<ul>
<li><p>保存数据</p>
<p>  当某个节点得到了新加入的数据（K/V），它会先计算自己与新数据的 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。</p>
<p>  如果计算下来，自己与 key 的距离最小，那么这个数据就保持在自己这里。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。</p>
</li>
<li><p>获取数据</p>
<p> 当某个节点接收到查询数据的请求（key），它会先计算自己与 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。</p>
<p>如果计算下来，自己与 key 的距离最小，那么就在自己这里找有没有 key 对应的 value。有的话就返回 value，没有的话就报错。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。</p>
</li>
</ul>
</li>
</ul>
<h3 id="3-Chord-协议"><a href="#3-Chord-协议" class="headerlink" title="3. Chord 协议"></a>3. Chord 协议</h3><ul>
<li>概述</li>
</ul>
<p>Chord 诞生于2001年。第一批 DHT 协议都是在那年涌现的，另外几个是：CAN、Tapestry、Pastry。</p>
<ul>
<li><p>拓扑结构——环形</p>
<p>  当初设计“一致散列”主要是为了解决“节点动态变化”这个难点（前面有提及）。为了解决这个难点，“一致散列”把散列值空间（keyspace）构成一个【环】。对于 m 比特的散列值，其范围是 [0, 2m-1]。你把这个区间头尾相接就变成一个环，其周长是 2m。然后对这个环规定了一个移动方向（比如顺时针）。</p>
</li>
</ul>
<pre><code>假设有某个节点A，距离它最近的是节点B（以顺时针方向衡量距离）。那么称 B 是 A 的【继任】（successor），A 是 B 的【前任】（predecessor）。

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">数据隶属于【距离最小】的节点。以 m=6 的环形空间为例：</span><br><span class="line">数据区间 [5,8] 隶属于节点8</span><br><span class="line">数据区间 [9,15] 隶属于节点15</span><br><span class="line">......</span><br><span class="line">数据区间 [59,4] 隶属于节点4（注：“6比特”的环形空间，63之后是0）</span><br></pre></td></tr></table></figure></code></pre><ul>
<li><p>路由机制</p>
<ul>
<li><p>基本路由（简单遍历）</p>
<p>  当收到请求（key），先看 key 是否在自己这里。如果在自己这里，就直接返回信息；否则就把 key 转发给自己的继任者。以此类推。<br>　　这种玩法的时间复杂度是 O(N)。对于一个节点数很多的 DHT 网络，这种做法显然非常低效。</p>
</li>
<li><p>高级路由（Finger Table）</p>
<p>  “Finger Table”是一个列表，最多包含 m 项（m 就是散列值的比特数），每一项都是节点 ID。 每一个节点都有个路由表</p>
</li>
</ul>
</li>
</ul>
<pre><code>假设当前节点的 ID 是 n，那么表中第 i 项的值是：successor( (n + 2i) mod 2m ) 当收到请求（key），就到“Finger Table”中找到【最大的且不超过 key】的那一项，然后把 key 转发给这一项对应的节点。有了“Finger Table”之后，时间复杂度可以优化为 O(log N)。`跳跃式查询`</code></pre><ul>
<li><p>节点的加入</p>
<ul>
<li>任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。</li>
<li>A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）</li>
<li>A 通过跟 B 进行查询，找到自己这个 ID 在环上的接头人。也就是——找到自己这个 ID 对应的“继任”（假设叫 C）与“前任”（假设叫 D）</li>
<li>　接下来，A 需要跟 C 和 D 进行一系列互动，使得自己成为 C 的前任，以及 D 的继任。这个互动过程，大致类似于在双向链表当中插入元素</li>
</ul>
</li>
<li><p>节点的【正常】退出</p>
<ul>
<li>如果某个节点想要主动离开这个 DHT 网络，按照约定需要作一些善后的处理工作。比如说，通知自己的前任去更新其继任者……<br>　　这些善后处理，大致类似于在双向链表中删除元素</li>
</ul>
</li>
<li><p>节点的【异常】退出</p>
<ul>
<li><p>作为一个分布式系统，任何节点都有可能意外下线（也就是说，来不及进行善后就挂掉了）</p>
<p>  假设 节点A 的继任者【异常】下线了，那么 节点A 就抓瞎了。咋办捏？为了保险起见，Chord 引入了一个“继任者候选列表”的概念。每个节点都用这个列表来包含：距离自己最近的 N 个节点的信息，顺序是【由近到远】。一旦自己的继任者下线了，就在列表中找到一个【距离最近且在线】的节点，作为新的继任者。然后 节点A 更新该列表，确保依然有 N 个候选。更新完“继任者候选列表”后，节点A 也会通知自己的前任，那么 A 的前任也就能更新自己的“继任者候选列表”。</p>
</li>
</ul>
</li>
</ul>
<h3 id="4-Kademlia（Kad）协议"><a href="#4-Kademlia（Kad）协议" class="headerlink" title="4. Kademlia（Kad）协议"></a>4. Kademlia（Kad）协议</h3><ul>
<li><p>拓扑结构——二叉树</p>
<ul>
<li><p>散列值的预处理</p>
<p>  Kad 也采用了“node ID 与 data key 同构”的设计思路。然后 Kad 采用某种算法把 key 映射到一个二叉树，每一个 key 都是这个二叉树的【叶子】。在映射之前，先做一下预处理。</p>
<ol>
<li>先把 key 以二进制形式表示。</li>
<li>把每一个 key 缩短为它的【最短唯一前缀】。</li>
</ol>
</li>
</ul>
</li>
</ul>
<pre><code>- 散列值的映射

    完成上述的预处理后，接下来的映射规则是：

    1. 先把 key 以二进制形式表示，然后从高位到低位依次处理。
    2. 二进制的第 n 个数位就对应了二叉树的第 n 层
    3. 如果该位是1，进入左子树，是0则进入右子树（这只是人为约定，反过来处理也可以）
    4. 全部数位都处理完后，这个 key 就对应了二叉树上的某个【叶子】</code></pre><ul>
<li><p>距离算法——异或（XOR）</p>
<p>  接下来要聊的是 Kad 最精妙之处——采用 XOR（按比特异或操作）算法计算 key 之间的“距离”。这种搞法使得它具备了类似于“几何距离”的某些特性（下面用 ⊕ 表示 XOR）</p>
  <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">(A ⊕ B) == (B ⊕ A)	XOR 符合“交换律”，具备对称性。相比之下，Chord 的距离算法不对称</span><br><span class="line">(A ⊕ A) == 0	反身性，自身距离为零</span><br><span class="line">(A ⊕ B) &gt; 0	【不同】的两个 key 之间的距离必大于零</span><br><span class="line">(A ⊕ B) + (B ⊕ C) &gt;= (A ⊕ C)	三角不等式</span><br></pre></td></tr></table></figure>


</li>
</ul>
<ul>
<li><p>路由机制</p>
<ul>
<li><p>二叉树的拆分</p>
<p>对每一个节点，都可以【按照自己的视角】对整个二叉树进行拆分。</p>
<p>拆分的规则是：先从根节点开始，把【不包含】自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。</p>
<p>Kad 默认的散列值空间是 m=160（散列值有 160 比特），因此拆分出来的子树【最多】有 160 个（考虑到实际的节点数【远远小于】2160，子树的个数会明显小于 160）。</p>
<p>对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到 n 个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这 n 个节点进行递归路由，从而到达整个二叉树的【任何一个】节点</p>
</li>
</ul>
</li>
<li><p>K-桶（K-bucket） </p>
<p>  每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（请始终牢记：分布式系统的节点是动态变化滴），光知道【一个】显然是不够滴，需要知道【多个】才比较保险。</p>
<p>  所以 Kad 论文中给出了一个“K-桶（K-bucket）”的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个【系统级】的常量。由使用 Kad 的软件系统自己设定（比如 BT 下载使用的 Kad 网络，K 设定为 8）。</p>
<p>  K 桶其实就是【路由表】。对于某个节点而言，如果【以它自己为视角】拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的【上限】是 K。说 K 只是一个【上限】，是因为有两种情况使得 K 桶的尺寸会小于 K。</p>
<ol>
<li>距离越近的子树就越小。如果整个子树【可能存在的】节点数小于 K，那么该子树的 K 桶尺寸永远也不可能达到 K。</li>
<li>有些子树虽然实际上线的节点数超过 K，但是因为种种原因，没有收集到该子树足够多的节点，这也会使得该子树的 K 桶尺寸小于 K。</li>
</ol>
</li>
<li><p>K-桶（K-bucket）的刷新机制</p>
<ul>
<li><p><code>主动收集节点</code>　        　</p>
<p>  任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新 K 桶中的节点信息</p>
</li>
<li><p><code>被动收集节点</code></p>
<p>  如果收到其它节点发来的请求（协议类型 FIND_NODE 或 FIND_VALUE），会把对方的 ID 加入自己的某个 K 桶中。 </p>
</li>
<li><p><code>探测失效节点</code></p>
<p>  Kad 还是支持一种探测机制（协议类型 PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。</p>
</li>
</ul>
</li>
</ul>
<ul>
<li><p>“并发请求”与“α 参数”</p>
<p>  “K桶”的这个设计思路【天生支持并发】。因为【同一个】“K桶”中的每个节点都是平等的，没有哪个更特殊；而且对【同一个】“K桶”中的节点发起请求，互相之间没有影响（无耦合）。</p>
<p>  所以 Kad 协议还引入了一个“α 参数”，默认设置为 3，使用 Kad 的软件可以在具体使用场景中调整这个 α 因子。</p>
<p>  当需要路由到某个“子树”，会从该子树对应的“K桶”中挑选【α 个节点】，然后对这几个节点【同时】发出请求。这么做有啥好处捏？俺在本文末尾聊“性能”和“安全性”时会具体介绍。</p>
</li>
<li><p>节点的加入</p>
<ul>
<li>任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。</li>
<li>A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）</li>
<li>A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）</li>
<li>B 收到该请求之后，（如前面所说）会先把 A 的 ID 加入自己的某个 K 桶中。然后，根据 FIND_NODE 协议的约定，B 会找到【K个】最接近 A 的节点，并返回给 A。（B 怎么知道哪些节点接近 A 捏？这时候，【用 XOR 表示距离】的算法就发挥作用啦）</li>
<li>A 收到这 K 个节点的 ID 之后，（仅仅根据这批 ID 的值）就可以开始初始化自己的 K 桶。</li>
<li>然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型 FIND_NODE），如此往复（递归），直至 A 建立了足够详细的路由表。</li>
</ul>
</li>
<li><p>节点的退出</p>
<p>  与 Chord 不同，Kad 对于节点退出没有额外的要求（没有“主动退出”的说法）。<br>　　所以，Kad 的节点想离开 DHT 网络不需要任何操作（套用徐志摩的名言：悄悄的我走了，正如我悄悄的来）</p>
</li>
</ul>
<h3 id="5-参考资料"><a href="#5-参考资料" class="headerlink" title="5. 参考资料"></a>5. 参考资料</h3><ul>
<li><a href="https://colobu.com/2018/03/26/distributed-hash-table/" target="_blank" rel="noopener">https://colobu.com/2018/03/26/distributed-hash-table/</a></li>
<li><a href="https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html" target="_blank" rel="noopener">https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html</a></li>
</ul>

    </div>

    
    
    
        
      
        <div id="reward-container">
  <div>坚持原创技术分享，您的支持将鼓励我继续创作, 一个耿直的笑脸~</div>
  <button id="reward-button" disable="enable" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
        
      
      <div style="display: inline-block">
        <img src="/images/wechatpay.jpg" alt="Levon 微信支付">
        <p>微信支付</p>
      </div>
        
      
      <div style="display: inline-block">
        <img src="/images/alipay.jpg" alt="Levon 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

      

      <footer class="post-footer">
          
            
          
          <div class="post-tags">
            
              <a href="/tags/dht/" rel="tag"># dht</a>
            
          </div>
        

        

          <div class="post-nav">
            <div class="post-nav-next post-nav-item">
              
                <a href="/p/1ea24e2a.html" rel="next" title="Kademlia_DHT_KRPC_BitTorrent协议">
                  <i class="fa fa-chevron-left"></i> Kademlia_DHT_KRPC_BitTorrent协议
                </a>
              
            </div>

            <span class="post-nav-divider"></span>

            <div class="post-nav-prev post-nav-item">
              
                <a href="/p/1b9bff9b.html" rel="prev" title="vim插件管理_vimrc配置和拷贝系统剪贴板">
                  vim插件管理_vimrc配置和拷贝系统剪贴板 <i class="fa fa-chevron-right"></i>
                </a>
              
            </div>
          </div>
        
      </footer>
    
  </div>
  
  
  
  </article>

  </div>


          </div>
          
    
    
  <div class="comments" id="comments">
    <div id="disqus_thread">
      <noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript>
    </div>
  </div>
  
  

        </div>
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">
        
        
        
        
      

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#1-如何实现散列表"><span class="nav-number">1.</span> <span class="nav-text">1. 如何实现散列表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#2-分布式散列表-DHT"><span class="nav-number">2.</span> <span class="nav-text">2. 分布式散列表 DHT</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#2-1-P2P-技术路线"><span class="nav-number">2.0.1.</span> <span class="nav-text">2.1 P2P 技术路线</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#2-2-DHT-难点"><span class="nav-number">2.0.2.</span> <span class="nav-text">2.2 DHT 难点</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#2-3-DHT-难点解决"><span class="nav-number">2.0.3.</span> <span class="nav-text">2.3 DHT 难点解决</span></a></li></ol></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-Chord-协议"><span class="nav-number">3.</span> <span class="nav-text">3. Chord 协议</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#4-Kademlia（Kad）协议"><span class="nav-number">4.</span> <span class="nav-text">4. Kademlia（Kad）协议</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-参考资料"><span class="nav-number">5.</span> <span class="nav-text">5. 参考资料</span></a></li></ol></div>
        
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
      src="/images/avatar.jpg"
      alt="Levon">
  <p class="site-author-name" itemprop="name">Levon</p>
  <div class="site-description" itemprop="description">Never Give Up</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        
          <a href="/archives/">
        
          <span class="site-state-item-count">127</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-categories">
        
          
            <a href="/categories/">
          
        
        <span class="site-state-item-count">34</span>
        <span class="site-state-item-name">分类</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-tags">
        
          
            <a href="/tags/">
          
        
        <span class="site-state-item-count">76</span>
        <span class="site-state-item-name">标签</span>
        </a>
      </div>
    
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://github.com/unix2dos" title="GitHub &rarr; https://github.com/unix2dos" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="mailto:levonfly@gmail.com" title="E-Mail &rarr; mailto:levonfly@gmail.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://twitter.com/levonfly" title="Twitter &rarr; https://twitter.com/levonfly" rel="noopener" target="_blank"><i class="fa fa-fw fa-twitter"></i>Twitter</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://weibo.com/l6241425" title="Weibo &rarr; https://weibo.com/l6241425" rel="noopener" target="_blank"><i class="fa fa-fw fa-weibo"></i>Weibo</a>
      </span>
    
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Levon</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-area-chart"></i>
    </span>
    <span title="站点总字数">507k</span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">7:41</span>
</div>

        












        
      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js?v=3.1.0"></script>
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
<script src="/js/utils.js?v=7.4.0"></script><script src="/js/motion.js?v=7.4.0"></script>
<script src="/js/schemes/pisces.js?v=7.4.0"></script>

<script src="/js/next-boot.js?v=7.4.0"></script>



  
  <script>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>








  <script src="/js/local-search.js?v=7.4.0"></script>














  

  

  

<script>
  function loadCount() {
    var d = document, s = d.createElement('script');
    s.src = 'https://levonfly.disqus.com/count.js';
    s.id = 'dsq-count-scr';
    (d.head || d.body).appendChild(s);
  }
  // defer loading until the whole page loading is completed
  window.addEventListener('load', loadCount, false);
</script>
<script>
  function disqus_config() {
    this.page.url = "https://unix2dos.github.io/p/2c46e603.html";
    this.page.identifier = "p/2c46e603.html";
    this.page.title = 'dht分布式散列表和kad介绍';};
  function loadComments() {
    if (window.DISQUS) {
      DISQUS.reset({
        reload: true,
        config: disqus_config
      });
    } else {
      var d = document, s = d.createElement('script');
      s.src = 'https://levonfly.disqus.com/embed.js';
      s.setAttribute('data-timestamp', '' + +new Date());
      (d.head || d.body).appendChild(s);
    }
  }
    window.addEventListener('load', loadComments, false);
  
</script>

</body>
</html>
